package cn.edu.zzuli.linkedlist;

public class SingleLinkedListDemo {

    public static void main(String[] args) {

        //创建链表
        SingleLinkedList list = new SingleLinkedList();
        SingleLinkedList list2 = new SingleLinkedList();

        //创建节点数据
        HeroNode node1 = new HeroNode(1,"宋江","及时雨");
        HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
        //HeroNode node3 = new HeroNode(3,"吴用","智多星");

        HeroNode node4 = new HeroNode(4,"gangtiexia","gangtiexia");
        HeroNode node5 = new HeroNode(5,"zhizhuxia","zhizhuxia");
        //HeroNode node6 = new HeroNode(6,"yehouxia","yehouxia");

        // list.add(node1);
        // list.add(node3);
        // list.add(node2);

        list.addByOrder(node1);
        // list.addByOrder(node3);
        // list.addByOrder(node6);

        list2.addByOrder(node2);
        list2.addByOrder(node4);
        list2.addByOrder(node5);

        // list.list();

        // list.update(new HeroNode(3, "无用", "智多星"));
        // System.out.println("修改后的链表信息");
        // list.list();


        // list.delete(node1);
        // System.out.println("删除后的链表信息");
        // list.list();


        // System.out.println("当前链表有效节点："+ list.getSize());
        // System.out.println(list.findLastIndexNode(1));

        // list.reverse();

        System.out.println("list1：");
        list.list();
        
        System.out.println("list2：");
        list2.list();

        SingleLinkedList merge = SingleLinkedList.merge(list, list2);
        System.out.println("合并后：");
        merge.list();
    }

}

class SingleLinkedList {

    //这是一个头节点，头节点不必存放信息
    private HeroNode head = new HeroNode(0,"","");


    //向链表中添加新元素
    public void add(HeroNode node) {

        //用一个临时的辅助指针来代替 头指针进行遍历
        HeroNode temp = head;

        //循环遍历到最后一个节点
        while (true) {
            //如果temp.next == null,说明当前节点为最后一个节点
            if (temp.next == null) {
                break;
            }

            // temp 指针后移，指向下一个节点
            temp = temp.next;
             
        }

        //将最后一个节点 next指向新的元素
        temp.next = node;
    }

    public void addByOrder(HeroNode node) {
        //用一个临时的辅助指针来代替 头指针进行遍历
        HeroNode temp = head;

        //用来判断是否找到 要修改节点
        boolean flag = false;

        //循环遍历到最后一个节点
        while (true) {
            
            //如果temp.next == null,说明当前节点为最后一个节点
            if (temp.next == null) {
                break;
            }

            //如果要添加节点的编号已存在于链表中
            if (temp.next.no == node.no) {
                flag = true;
                break;
            }

            //想要按照顺序排列，我们一定要找到插入的位置
            //这个位置应该怎么找呢？一定是要找到 要加入位置的前一个节点（按照升序排列的情况下，降序则反之）
            // 比如，你现在的no是3，要加入的位置是链表中的no是2，和no是4的两个节点，你就需要找到2这个位置，而2.next.no此时是4
            //所以我们用2.next.no来与加入的节点的.no判断
            if (temp.next.no > node.no) {
                
                //先将节点3.next 指向节点4
                node.next = temp.next; 
                //再将节点2.next 指向 节点3
                temp.next = node;

                break;
            }

            // temp 指针后移，指向下一个节点
            temp = temp.next;
             
        }

        if (flag) {
            System.out.println("要添加的节点编号已存在于当前链表");
            return;
        }

        //将最后一个节点 next指向新的元素
        temp.next = node;

    }
        

    //遍历当前这个链表
    public void list() {
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }

        //这里我们不需要输出头节点，所以我们可以直接让辅助指针指向第一个节点
        HeroNode temp = head.next;

        while (true) {

            //这里因为我们要输出最后一个元素，所以不能 判断 temp.next == null
            if (temp == null) {
                break;
            }

            System.out.println(temp);
            temp = temp.next;
        }

    }

    //根据节点的 no进行修改
    public void update(HeroNode node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;

        //用来判断是否找到 要修改节点
        boolean flag = false;
        //找到需要修改的节点
        while(true) {

            if (temp == null) {
                //已经遍历完成
                break;
            }

            if (temp.no == node.no) {
                //找到该节点
                flag = true;
                break;
            }

            temp = temp.next;

        }

        if (flag) {
            temp.name = node.name;
            temp.nickName = node.nickName;
        } else {
            System.out.println("没有找到编号为"+node.no+"节点");
        }

    }

    public void delete(HeroNode node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head;
        boolean flag = false;
        

        while(true) {

            if (temp.next == null) {
                break;
            }

            if (temp.next.no == node.no) {
                //找到该节点前一个节点
                flag = true;
                break;
            }

            temp = temp.next;

        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到编号为"+node.no+"节点");
        }
    }


    //获取有效节点的个数
    public int getSize() {
        int size = 0;
        HeroNode temp = head.next;
        while ( temp != null) {
            size ++;
            temp = temp.next;
        }
        return size;
    }

    //获取倒数第 k 个节点
    public HeroNode findLastIndexNode(int index) {
        if (head.next == null) {
            return null;
        }

        HeroNode temp = head.next;
        int size = getSize();

        //验证 index 有效性
        if (index <= 0 || index > size) {
            return null;
        } 

        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }

        return temp;
    }


    //将单链表进行反转
    //利用头插法
    public void reverse() {
        //如果链表为 null 或者只有一个节点，说明不需要反转
        if (head.next == null || head.next.next == null) {
            return;
        }

        HeroNode temp = head.next;

        System.out.println(temp == head.next);

        //用来表示反转链表的 头节点
        HeroNode reverseHead = new HeroNode(0,"","");;

        //指向当前节点的下一个节点
        HeroNode next = null;

        while (temp != null) {
            //先把下一个节点的信息保存下来
            next = temp.next;

            //将反转链表头节点的 下一个节点保存到 当前节点的next 域里
            temp.next = reverseHead.next;
            //将当前节点放到 头节点的 next域里
            reverseHead.next = temp;
            //读取下个节点的信息
            temp = next;
        }

        head.next = reverseHead.next;
    }

    public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
        //合并的新链表
        SingleLinkedList newList = new SingleLinkedList();
        //新链表的辅助接点
        HeroNode newTemp = newList.head;

        //需要两个辅助节点,指向头节点
        HeroNode temp1 = list1.head.next;
        HeroNode temp2 = list2.head.next;

        //现在按升序排列
        while(true) {

            if ( temp1 == null || temp2 == null) {
                break;
            }

            if (temp1.no <= temp2.no) {
                newTemp.next = temp1;
                temp1 = temp1.next;
                newTemp = newTemp.next;
                continue;
            }
            
            if (temp1.no > temp2.no) {
                newTemp.next = temp2;
                temp2 = temp2.next;
                newTemp = newTemp.next;
            }

        }

        if (temp1 == null) {
            newTemp.next = temp2;
        }

        if (temp2 == null) {
            newTemp.next = temp1;
        }

        return newList;
    }



}

class HeroNode {
    int no;
    String name;
    String nickName;
    //指向下一个节点
    HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "[HeroNode no=" + no + ", name=" + name + ", nickName=" + nickName + "]" ;
    }

    
}